package main

import (
	"fmt"
	. "go_data_structures_and_algorithms/tool"
)

type Stack struct {
	Arr    []int
	length int
}

func NewStack() Stack {
	return Stack{Arr: make([]int, 100), length: 0}
}

func (s *Stack) push(value int) {
	s.Arr[s.length] = value
	s.length++
}

func (s *Stack) pop() int {

	if s.length > 0 {
		value := s.Arr[s.length-1]
		s.length--
		return value
	} else {
		fmt.Println("栈为空不能弹出元素，默认弹出-1")
		return -1
	}

}
func (s *Stack) Print() {
	for i := s.length - 1; i >= 0; i-- {
		fmt.Print(s.Arr[i], " ")

	}
}

func IsPalindrome(node *ListNode) bool {
	if node == nil || node.Next == nil {
		return false

	}

	head := node
	stack := NewStack()
	for head != nil {

		stack.push(head.Val)
		head = head.Next
	}

	head = node

	for i := stack.length - 1; i >= 0; i-- {
		if stack.pop() != head.Val {
			return false
		}
		head = head.Next
	}

	return true
}
func main() {

	node1 := &ListNode{
		1,
		nil,
	}
	node2 := &ListNode{
		2,
		nil,
	}
	node3 := &ListNode{
		3,
		nil,
	}
	node4 := &ListNode{
		3,
		nil,
	}
	node5 := &ListNode{
		2,
		nil,
	}
	node6 := &ListNode{
		1,
		nil,
	}

	node1.Next = node2
	node2.Next = node3
	node3.Next = node4
	node4.Next = node5
	node5.Next = node6
	palindrome := IsPalindrome(node1)
	fmt.Println(palindrome)
}
